package org.example.myleet.p628;

import java.util.Arrays;

public class Solution2 {
    /**
     * 3 ms
     * 线性扫描
     */
    public int maximumProduct(int[] nums) {
        if (nums.length == 3) {
            //刚好3个数则直接返回，否则就是最少4个数
            return nums[0] * nums[1] * nums[2];
        }
        //初始化找出3个依次最大的数
        int[] initArr = new int[]{nums[0],nums[1],nums[2]};
        Arrays.sort(initArr);
        int max1 = initArr[2], max2 = initArr[1], max3 = initArr[0];
        for (int i=3; i<nums.length; i++) {
            if (nums[i] > max1) {
                max3 = max2;
                max2 = max1;
                max1 = nums[i];
                continue;
            }if (nums[i] <= max1 && nums[i] > max2) {
                max3 = max2;
                max2 = nums[i];
                continue;
            }
            if (nums[i] <= max2 && nums[i] > max3) {
                max3 = nums[i];
            }
        }
        //再找出2个依次最小的数
        int min1 = max2, min2 = max1;
        for (int i=0; i<nums.length; i++) {
            if (nums[i] < min1) {
                min2 = min1;
                min1 = nums[i];
                continue;
            }
            if (nums[i] >= min1 && nums[i] < min2) {
                min2 = nums[i];
            }
        }
        return Math.max(max1 * max2 * max3, min1 * min2 * max1);
    }
}
